package com.xw.class12;

import java.util.LinkedList;

/**
 * @author XW
 * @data 2023/8/22 14:24
 * @description 判断一棵树是否是完全二叉树
 *              完全二叉树的定义：若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，
 *                  第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
 */
public class Code01_IsCBT {

    class Node{
        public int val;
        public Node left;
        public Node right;

        public Node(int val){
            this.val = val;
        }
    }

    public static boolean judgeIsCBT(Node head){
        if(null == head){
            return true;
        }
        LinkedList<Node> nodes = new LinkedList<>();
        //是否遇到过左右不双全的节点
        boolean leaf = false;
        Node l = null;
        Node r = null;
        nodes.add(head);
        while (!nodes.isEmpty()){
            Node node = nodes.poll();
            l = node.left;
            r = node.right;
            //如果某个节点有右无左 直接返回false 或者前面有节点已经是左右不双全了 那么该节点只能是叶子节点，否则返回false
            if((l == null && r != null) || (leaf && (l != null || r != null ))){
                return false;
            }
            if(l != null){
                nodes.add(l);
            }
            if(r != null){
                nodes.add(r);
            }
            //左右不双全 leaf = true
            if(l== null || r==null) {
                leaf = true;
            }
        }
        return true;

    }
}
